package BinaryTree;

//二叉树的层序遍历：https://leetcode.cn/problems/binary-tree-level-order-traversal/description/
//时间复杂度: O(n)
import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;
class TreeNode {
	  int val;
	  TreeNode left;
	  TreeNode right;
	  TreeNode() {}
	  TreeNode(int val) { this.val = val; }
	  TreeNode(int val, TreeNode left, TreeNode right) {
	      this.val = val;
	      this.left = left;
	      this.right = right;
	  }
}

public class Code1 {
	//普通的bfs，不推荐
	public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> ans=new ArrayList<>();
        if(root!=null){
            Map<TreeNode,Integer> levels=new HashMap<>();
            Queue<TreeNode> queue=new LinkedList<>();
            queue.add(root);
            levels.put(root,0);
            while(!queue.isEmpty()){
                TreeNode cur=queue.poll();  //队头出队，并保持对头节点
                
                int level=levels.get(cur);  //获取当前节点所在层
                
                //处理第k层时，层数level=k，ans的大小也为k
                //如果处理了新的一层，比如 k-> k+1
                //显然，ans当前只存储了前k层的数据，因此其也需要扩一层，即新增一个元素
                
                //=》由上可知，一旦level==ans.size()即代表需要新增一个元素
                if(level==ans.size()){    
                    ans.add(new ArrayList<>());
                }
                
                //ans.get(level): 由于level从0开始计算，因此level可以对应数组ans的下标
                //                =》 返回level处的元素，元素为ArrayList
                //ans.get(level)拿到第k层的待插入数组，数据插入即可
                ans.get(level).add(cur.val);
         
                //当前节点有孩子，则入队列，孩子所在层显然为父节点所在层level+1
                if(cur.left!=null){
                    queue.add(cur.left);
                    levels.put(cur.left,level+1);
                }
                if(cur.right!=null){
                    queue.add(cur.right);
                    levels.put(cur.right,level+1);
                }
            }
        }
        return ans;
    }

}
